package com.sheng.leetcode.year2023.month11.day01;

import org.junit.Test;

import java.util.*;

/**
 * @author by ls
 * @date 2023/11/1
 * <p>
 * 2127. 参加会议的最多员工数<p>
 * <p>
 * 一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。<p>
 * 员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。<p>
 * 给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：favorite = [2,2,1,2]<p>
 * 输出：3<p>
 * 解释：<p>
 * 上图展示了公司邀请员工 0，1 和 2 参加会议以及他们在圆桌上的座位。<p>
 * 没办法邀请所有员工参与会议，因为员工 2 没办法同时坐在 0，1 和 3 员工的旁边。<p>
 * 注意，公司也可以邀请员工 1，2 和 3 参加会议。<p>
 * 所以最多参加会议的员工数目为 3 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：favorite = [1,2,0]<p>
 * 输出：3<p>
 * 解释：<p>
 * 每个员工都至少是另一个员工喜欢的员工。所以公司邀请他们所有人参加会议的前提是所有人都参加了会议。<p>
 * 座位安排同图 1 所示：<p>
 * - 员工 0 坐在员工 2 和 1 之间。<p>
 * - 员工 1 坐在员工 0 和 2 之间。<p>
 * - 员工 2 坐在员工 1 和 0 之间。<p>
 * 参与会议的最多员工数目为 3 。<p>
 * <p>
 * 示例 3：<p>
 * 输入：favorite = [3,0,1,4,1]<p>
 * 输出：4<p>
 * 解释：<p>
 * 上图展示了公司可以邀请员工 0，1，3 和 4 参加会议以及他们在圆桌上的座位。<p>
 * 员工 2 无法参加，因为他喜欢的员工 0 旁边的座位已经被占领了。<p>
 * 所以公司只能不邀请员工 2 。<p>
 * 参加会议的最多员工数目为 4 。<p>
 * <p>
 * 提示：<p>
 * n == favorite.length<p>
 * 2 <= n <= 10^5<p>
 * 0 <= favorite[i] <= n - 1<p>
 * favorite[i] != i<p>
 */
public class LeetCode2127 {

    @Test
    public void test01() {
//        int[] favorite = {2, 2, 1, 2};
//        int[] favorite = {1, 2, 0};
        int[] favorite = {3, 0, 1, 4, 1};
        System.out.println(new Solution().maximumInvitations(favorite));
    }
}

class Solution {
    public int maximumInvitations(int[] favorite) {
        return Math.max(maxCycle(favorite), topologicalSort(favorite));
    }

    private int maxCycle(int[] fa) {
        int n = fa.length;
        boolean[] vis = new boolean[n];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (vis[i]) {
                continue;
            }
            List<Integer> cycle = new ArrayList<>();
            int j = i;
            while (!vis[j]) {
                cycle.add(j);
                vis[j] = true;
                j = fa[j];
            }
            for (int k = 0; k < cycle.size(); ++k) {
                if (cycle.get(k) == j) {
                    ans = Math.max(ans, cycle.size() - k);
                }
            }
        }
        return ans;
    }

    private int topologicalSort(int[] fa) {
        int n = fa.length;
        int[] indeg = new int[n];
        int[] dist = new int[n];
        Arrays.fill(dist, 1);
        for (int v : fa) {
            indeg[v]++;
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            if (indeg[i] == 0) {
                q.offer(i);
            }
        }
        int ans = 0;
        while (!q.isEmpty()) {
            int i = q.pollFirst();
            dist[fa[i]] = Math.max(dist[fa[i]], dist[i] + 1);
            if (--indeg[fa[i]] == 0) {
                q.offer(fa[i]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (i == fa[fa[i]]) {
                ans += dist[i];
            }
        }
        return ans;
    }
}
